class Solution {
    public int findKthLargest(int[] nums, int k) {
        //使用大根堆排序,正序
        HeapSort(nums);
        return nums[nums.length-k];
    }

    //堆排序
    private void HeapSort(int[] nums) {
        //先排成大根堆
        createBigHeap(nums);
        int end = nums.length-1;
        while(end >= 0) {
            swap(nums,0,end);
            end--;
            //最大的就在前三个里面呢,只需要从前三个里面找到就行
            downHeapSort(nums,0,end);
        }
    }

    //建大根堆
    private void createBigHeap(int[] nums) {
        //从倒数第二层开始排
        for(int i = (nums.length-1-1)/2;i>=0;i--) {
            downHeapSort(nums,i,nums.length);
        }
    }

    private void downHeapSort(int[] nums,int parent,int len) {
        int child = (parent*2) + 1;
        while(child < len) {
            if(child+1 < len && nums[child] < nums[child+1]) {
                child++;
            }
            if(nums[child] > nums[parent]) {
                swap(nums,parent,child);
            }
            parent = child;
            child = (child*2)+1;
        }
    }

    private void swap(int[] num,int a,int b) {
        int tem = num[a];
        num[a] = num[b];
        num[b] = tem;
    }


}